目標：
這題主要目的在於闡明In-place algorithm的含義，
以及使用In-place的條件下會受到的限制。

原題：

Question:
Given a sorted nums array, remove the duplicates in-place such that each element appears only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.

Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.

分析/解題：
題目要求將一個已排序陣列中所有的重複數字刪去，
使得這個陣列的每個數字只出現一次，並且必須要以in-place的方式來處理。
最終處理過後，回傳新陣列的長度。

題目其實並不困難，設定一個i用來記錄目前存放到哪個位置，
再設定一個j用以完整遍歷整個陣列，
每當發現有不同的數字時，就將j的數字塞到i的位置，再往下推進即可。
最後由於要回傳的是新陣列的長度，所以應該要回傳i+1。(陣列由0開始)

這邊要順便提到的一個名詞叫in-place algorithm。
所謂的in-place，就是指所有的操作修改，除了一些計數用的變數外，
基本上都在原先的資料結構內解決，像這題就是完全只有操作原陣列。
如果沒有這樣的限制，這題也是可以使用ArrayList，每
當發現一個不同的數就將其往List尾端加，最後再將其轉為array，
同樣可以得到解，但它的空間複雜度就會變成O(N)，
因為我們開了一組額外的記憶體來存放它。

所以in-place algorithm會應用在一些不希望大量增加記憶體使用量的狀況，
且在這個限制條件下，有時候我們不一定能像這題這樣，
得到跟非in-place時一樣時間複雜度的解法。

所以in-place algorithm通常會有拿時間換取空間效率的狀況。
總之，如果原先的資料被修改或打亂也沒關係的話，
就有使用in-place algorithm的機會，也有可能會被面試官問到，
但請務必謹慎地確認是否這個狀況下，
你真的會必須用比較差的時間複雜度達到相同的目的。

Java:

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
}

Python:

class Solution:
    def removeDuplicates(self, nums):
        if not nums: return 0
        i, j = 0, 1
        while j < len(nums):
            if nums[i] != nums[j]:
                i += 1
                nums[i] = nums[j]
            j += 1
        return i + 1

面試實際可能會遇到的問題：
「時間複雜度跟空間複雜度為？」(O(N), O(1))

「如果不要求in-place，改成新開list/arraylist來做會比較快嗎？」
(不會，因為時間複雜度相同，但要額外花時間做記憶體配置)

「如果題目今天給的是未排序陣列要去除duplicate，
但不用in-place，也不用保留順序的話？」
(使用HashMap/dict，將整個陣列掃過一遍，最後遍歷輸出)
(時間/空間複雜度為O(N), O(N))

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0035. Search Insert Position (Easy)